{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Homogenous Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countHomogenous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计同质子字符串的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，返回<em> </em><code>s</code><em> </em>中 <strong>同质子字符串</strong> 的数目。由于答案可能很大，只需返回对 <code>10<sup>9</sup> + 7</code> <strong>取余 </strong>后的结果。</p>\n",
    "\n",
    "<p><strong>同质字符串</strong> 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同质字符串。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中的一个连续字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abbcccaa\"\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>同质子字符串如下所列：\n",
    "\"a\"   出现 3 次。\n",
    "\"aa\"  出现 1 次。\n",
    "\"b\"   出现 2 次。\n",
    "\"bb\"  出现 1 次。\n",
    "\"c\"   出现 3 次。\n",
    "\"cc\"  出现 2 次。\n",
    "\"ccc\" 出现 1 次。\n",
    "3 + 1 + 2 + 1 + 3 + 2 + 1 = 13</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"xy\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>同质子字符串是 \"x\" 和 \"y\" 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"zzzzz\"\n",
    "<strong>输出：</strong>15\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写字符串组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-homogenous-substrings](https://leetcode.cn/problems/count-number-of-homogenous-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-homogenous-substrings](https://leetcode.cn/problems/count-number-of-homogenous-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abbcccaa\"', '\"xy\"', '\"zzzzz\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(s)\n",
    "        i=0\n",
    "        cnt =0\n",
    "        l=0\n",
    "        while i<n:\n",
    "            start=i\n",
    "            i+=1\n",
    "            while i<n and s[i]==s[i-1]:\n",
    "                i+=1\n",
    "            l =i-start\n",
    "            cnt += (l+1)*l//2\n",
    "        return cnt%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        x = Counter(s)\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for _,k in x.items():\n",
    "            ans+=k\n",
    "        mod = int(1e9+7)\n",
    "        while i < n:\n",
    "            j = i+1\n",
    "            while j < n and s[j]==s[i]:\n",
    "                ans=(ans+j-i)%mod\n",
    "                j+=1\n",
    "            i = j\n",
    "       \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        o = 0\n",
    "        for i, j in itertools.groupby(s):\n",
    "            l = len(list(j))\n",
    "            o += ((l * (l+1)) // 2)\n",
    "            # print((l * (l+1)) // 2)\n",
    "            o = o % (10**9 + 7)\n",
    "        return o"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n*(n+1))//2\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        MOD = int(1e9 + 7)\n",
    "        i, n = 0, len(s)\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and s[i] == s[j]:\n",
    "                j += 1\n",
    "            cnt = j - i\n",
    "            ans = (ans + (cnt + 1) * cnt // 2) % MOD\n",
    "            i = j\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i<n:\n",
    "            j = i+1\n",
    "            while j<n and s[j]==s[j-1]:\n",
    "                j +=1\n",
    "            tmp = j-i\n",
    "            if tmp==1:\n",
    "                ans +=1\n",
    "            else:\n",
    "                ans += int((tmp+1)*tmp/2)\n",
    "            i = j\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res=0\n",
    "        for k,g in groupby(s):\n",
    "            n=len(list(g))\n",
    "            res+=(n+1)*n//2\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        def dfs(n:int)->int:\n",
    "            return n*(n+1) // 2\n",
    "        i,j,ans = 0,0,0\n",
    "        while i <= j and i < len(s):\n",
    "            if j < len(s) and s[i] == s[j]:\n",
    "                j += 1\n",
    "                continue\n",
    "            ans = (ans + dfs(j-i)) % mod\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        i,j = 0,0\n",
    "        res = 0\n",
    "        while j < len(s):\n",
    "            while j < len(s) and s[i] == s[j]:\n",
    "                j += 1\n",
    "            tmp = j-i\n",
    "            res += tmp*(tmp+1) // 2\n",
    "            if j < len(s) and s[i] != s[j]:\n",
    "                i = j\n",
    "        return res % (10**9+7)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        res=0\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if i<n-1 and s[i]!=s[i+1]:\n",
    "                res+=1\n",
    "                i+=1\n",
    "                continue\n",
    "            start=i\n",
    "            i+=1\n",
    "            while i<n and s[i-1]==s[i]:\n",
    "                i+=1\n",
    "            res+=(1+i-start)*(i-start)//2\n",
    "        return res%(7+10**9)        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and s[i] == s[i-1]:\n",
    "                i += 1\n",
    "            count = i - start\n",
    "            # while count:\n",
    "            #     ans += count\n",
    "            #     count -= 1\n",
    "            ans += count*(count+1) // 2\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        i, n = 0, len(s)\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and s[j] == s[i]:\n",
    "                j += 1\n",
    "            cnt = j - i\n",
    "            ans += (1 + cnt) * cnt // 2\n",
    "            ans %= mod\n",
    "            i = j\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        i, n, ans = 0, len(s), 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            while i < n and s[i] == s[start]: i += 1\n",
    "            ans = (ans + (i - start + 1) * (i - start) // 2)  % (10**9 + 7)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        count = 0\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            if (i == 0):\n",
    "                count = 1\n",
    "            elif (s[i] == s[i-1]):\n",
    "                count += 1\n",
    "            else:\n",
    "                res += (count*count + count)/2\n",
    "                count = 1\n",
    "        res += (count*count + count)/2\n",
    "        \n",
    "        return int(res) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        hashmap = collections.defaultdict(int)\n",
    "        ans = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        start = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if i == 0 or s[i] == s[i - 1]:\n",
    "                continue\n",
    "            else:\n",
    "                hashmap[s[start:i]] += 1\n",
    "                start = i\n",
    "        hashmap[s[start: len(s)]] += 1\n",
    "        for key, val in hashmap.items():\n",
    "            ans += (1 + len(key)) * len(key) // 2 * val\n",
    "        return ans % mod\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countHomogenous(self, s: str) -> int:\r\n",
    "        MOD = 10**9 + 7\r\n",
    "        n = len(s)\r\n",
    "        ans = l = 1\r\n",
    "        for i in range(1, n):\r\n",
    "            if s[i] == s[i-1]:\r\n",
    "                l += 1\r\n",
    "            else:\r\n",
    "                l = 1\r\n",
    "            ans += l % MOD\r\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and s[i] == s[i-1]:\n",
    "                i += 1\n",
    "            a = i - start\n",
    "            ans += (1 + a) * a / 2\n",
    "        return int(ans % (1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i = ans = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            cnt = 1\n",
    "            i += 1\n",
    "            while i < n and s[i - 1] == s[i]:\n",
    "                i += 1\n",
    "                cnt += i - start\n",
    "            ans += cnt\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = i = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            i += 1\n",
    "            while i < n and s[i] == s[i-1]:\n",
    "                i += 1\n",
    "            a = i - start\n",
    "            ans += (1 + a) * a // 2\n",
    "        return int(ans % (1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        i, n = 0, len(s)\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and s[j] == s[i]:\n",
    "                j += 1\n",
    "            cnt = j - i\n",
    "            ans += (1 + cnt) * cnt // 2\n",
    "            ans %= mod\n",
    "            i = j\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        index = 0\n",
    "        s_len = len(s)\n",
    "        ans = 0\n",
    "        flag = 10**9+7\n",
    "        while index< s_len:\n",
    "            start = index+1\n",
    "            while start<s_len and s[index] == s[start]:\n",
    "                start +=1\n",
    "            count = start-index\n",
    "            ans += count*(count+1)//2\n",
    "            ans%=flag\n",
    "            index = start\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        count = 0\n",
    "        lo, hi = 0, 0\n",
    "        while True:\n",
    "            if not hi < len(s):\n",
    "                break\n",
    "            while hi < len(s) and s[lo] == s[hi]:\n",
    "                hi += 1\n",
    "            count += ((hi-lo)+1)*(hi-lo)//2\n",
    "            lo = hi\n",
    "        return count % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, res, l = len(s), 0, 0\n",
    "        while l < n:\n",
    "            r = l + 1\n",
    "            while r < n and s[r] == s[r-1]:\n",
    "                r += 1\n",
    "            m = r - l\n",
    "            res += m * (m + 1) // 2\n",
    "            l = r\n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        ## count the continuous \n",
    "        i = 0\n",
    "        n = len(s)\n",
    "        MOD = pow(10,9)+7\n",
    "        tot = 0\n",
    "        while i < n:\n",
    "            cur = 1\n",
    "            j = i + 1\n",
    "            while j < n and s[i] == s[j]:\n",
    "                cur += 1\n",
    "                j += 1\n",
    "            tot = (tot + cur * (cur + 1)//2) % MOD\n",
    "            i = j\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            l = i\n",
    "            i += 1\n",
    "            while i < n and s[i] == s[i-1]:\n",
    "                i += 1\n",
    "            ans += (1 + i - l) * (i - l) // 2\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        l,r = 0,0\n",
    "        while r < len(s):\n",
    "            if s[r] == s[l]:\n",
    "                r += 1\n",
    "            else:\n",
    "                res += comb(r-l,2)+r-l\n",
    "                res %= MOD\n",
    "                l = r\n",
    "        res += comb(r-l,2)+r-l\n",
    "        return res % MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        i=0\n",
    "        ans=0\n",
    "        count=0\n",
    "        mod=10**9+7\n",
    "        while i<n:\n",
    "            if i>0 and s[i]==s[i-1]:\n",
    "                count+=1\n",
    "            else:\n",
    "                ans+=(1+count)*count//2\n",
    "                ans=ans%mod\n",
    "                count=1\n",
    "            i+=1\n",
    "        ans+=(1+count)*count//2\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        count,i=0,0\n",
    "        while i<n:\n",
    "            cur=1\n",
    "            while i<n-1 and s[i]==s[i+1]:\n",
    "                cur+=1\n",
    "                i+=1\n",
    "            count+=((cur+1)*cur//2)%1000000007\n",
    "            i+=1\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        while r < len(s):\n",
    "            while s[r] != s[l]:\n",
    "                l += 1\n",
    "            \n",
    "            res += r-l+1\n",
    "            r += 1\n",
    "        return res%(pow(10,9)+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < n:\n",
    "            start = i\n",
    "            while i < n - 1 and s[i] == s[i + 1]:\n",
    "                i += 1\n",
    "            x = i - start + 1\n",
    "            cnt = 0\n",
    "            while x > 0:\n",
    "                cnt += x \n",
    "                x -= 1\n",
    "            ans += cnt\n",
    "            i += 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        size = len(s)\n",
    "        i, j = 0, 0\n",
    "        C = 10**9+7\n",
    "        pre = \" \"\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c != pre:\n",
    "                res += cnt*(cnt+1)//2 % C\n",
    "                cnt = 1\n",
    "                pre = c\n",
    "            else:\n",
    "                cnt += 1\n",
    "        res += cnt*(cnt+1)//2 % C\n",
    "        return res % C\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        # 先用哈希表把子串存起来\n",
    "        # 同质还是要在一类的里面找\n",
    "        # 淘汰\n",
    "        sum = 0\n",
    "        i, n = 0, len(s)\n",
    "        while i<n:\n",
    "            start = i\n",
    "            while i<n and s[start] == s[i]:\n",
    "                i+=1\n",
    "            sum += ((i-start)/2) * (1 + (i-start))\n",
    "        return int(sum%(10**9+7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(s)\n",
    "        r = 0\n",
    "        ans = 0\n",
    "        while r<n:\n",
    "            tmp = 0\n",
    "            l = r\n",
    "            while r<n and s[l] == s[r]:\n",
    "                tmp += 1\n",
    "                r += 1\n",
    "            ans += (1+tmp)*tmp//2\n",
    "        return ans%mod\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        ans, l = 0, 0\n",
    "        cnt = Counter()\n",
    "        for r, c in enumerate(s):\n",
    "            cnt[c] += 1\n",
    "            while len(cnt) > 1:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    del cnt[s[l]]\n",
    "                l += 1\n",
    "            ans += r - l + 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        li = []\n",
    "        add_dic = dict()\n",
    "        string = s[0]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != string[0]:\n",
    "                li.append(string)\n",
    "                string = s[i]\n",
    "            else:\n",
    "                string += s[i]\n",
    "        li.append(string)\n",
    "        for str in li:\n",
    "            l = len(str)\n",
    "            if add_dic.get(l) is None:\n",
    "                add = (l + 1) * l // 2\n",
    "                add_dic[l] = add\n",
    "            else: \n",
    "                add = add_dic.get(l)  \n",
    "            res += add\n",
    "            res %= 10 ** 9 + 7\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        lst = []\n",
    "        s+=\"X\"\n",
    "        n, l, r = len(s), 0, 1\n",
    "        while r < n:\n",
    "            if s[l] == s[r]:\n",
    "                r += 1\n",
    "            else:\n",
    "                tmp = s[l:r]\n",
    "                lst.append(tmp)\n",
    "                l = r\n",
    "        \n",
    "        \n",
    "        ans = sum((len(v)+1)*len(v)//2 for v in lst)\n",
    "        return ans % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        def termial(x):\n",
    "            return sum(n for n in range(1, x + 1))\n",
    "        l = []\n",
    "        tmp = 0\n",
    "        ans = 0\n",
    "        for i in range(1, len(s)):\n",
    "            if s[tmp] != s[i]:\n",
    "                l.append(s[tmp:i])\n",
    "                tmp = i\n",
    "            i += 1\n",
    "        l.append(s[tmp:])\n",
    "        for substr in l:\n",
    "            ans += termial(len(substr))\n",
    "        return (ans % int(1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        lst = []\n",
    "        n, l, r = len(s), 0, 1\n",
    "        while r < n:\n",
    "            if s[l] == s[r]:\n",
    "                r += 1\n",
    "            else:\n",
    "                tmp = s[l:r]\n",
    "                lst.append(tmp)\n",
    "                l = r\n",
    "        lst.append(s[l:r])\n",
    "        \n",
    "        ans = sum((len(v)+1)*len(v)//2 for v in lst)\n",
    "        return ans % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        list1=[]\n",
    "        m=s[0]\n",
    "        for i in range(1,len(s)):  #8\n",
    "            if s[i]==s[i-1]:\n",
    "                m+=s[i]\n",
    "            else:\n",
    "                list1.append(m)\n",
    "                m=s[i]\n",
    "        list1.append(m)\n",
    "        d1=collections.Counter(list1)\n",
    "\n",
    "        h=0\n",
    "        for i in d1:\n",
    "            h+=(len(i)+1)*len(i)/2*d1[i]\n",
    "        return int(h)%(10**9+7)\n",
    "        \n",
    "\n",
    "        #(1+n)*n/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        l=[]\n",
    "        if len(s)==1:\n",
    "            return 1\n",
    "        i=0\n",
    "        for t in range(1,len(s)):\n",
    "            if s[t]!=s[i]:\n",
    "                l.append(s[i:t])\n",
    "                i=t\n",
    "            if t==len(s)-1:\n",
    "                l.append(s[i:])\n",
    "\n",
    "        for j in l:\n",
    "            n = len(j)\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        str_list = []\n",
    "        num = 1\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == s[i - 1]:\n",
    "                num += 1\n",
    "                if i == len(s) - 1:\n",
    "                    str_list.append(num * s[i - 1])\n",
    "                continue\n",
    "            else:\n",
    "                item = num * s[i - 1]\n",
    "                num = 1\n",
    "            str_list.append(item)\n",
    "            if i == len(s) - 1:\n",
    "                str_list.append(num * s[i])\n",
    "        n = 0\n",
    "        for a in str_list:\n",
    "            n += len(a) * (len(a) + 1) // 2\n",
    "        n %= 10**9 + 7\n",
    "        return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        t=1\n",
    "        res=0\n",
    "        for i in range(len(s)):\n",
    "            if i!=0 and s[i-1]==s[i]:\n",
    "                t+=1\n",
    "            if i!=0 and s[i-1]!=s[i]:\n",
    "                res+=((t+1)*t)//2\n",
    "                t=1\n",
    "            if i==len(s)-1:\n",
    "                res+=((t+1)*t)//2\n",
    "        return res%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        start, stop = 0, 1\n",
    "        l =[]\n",
    "        re = 0\n",
    "        while stop < n:\n",
    "            if s[start] != s[stop]:\n",
    "                l.append(s[start:stop])\n",
    "                start = stop \n",
    "            stop += 1\n",
    "        l.append(s[start:])\n",
    "        for e in l:\n",
    "            re += (1 + len(e)) * len(e) // 2\n",
    "        return re % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        li = []\n",
    "        #finished_dic = dict()\n",
    "        string = s[0]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != string[0]:\n",
    "                li.append(string)\n",
    "                string = s[i]\n",
    "            else:\n",
    "                string += s[i]\n",
    "        li.append(string)\n",
    "        for str in li:\n",
    "            add = (len(str) + 1) * len(str) // 2\n",
    "            res += add\n",
    "            res %= 10 ** 9 + 7\n",
    "            #finished_dic[str] = add\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        M = 10**9 + 7\n",
    "        i, j = 0, 0\n",
    "        res = []\n",
    "        while i < len(s) and j < len(s):\n",
    "            while j < len(s) and s[j] == s[i]:\n",
    "                j += 1\n",
    "            res.append(j-i)\n",
    "            i = j\n",
    "        ans = [n*(n+1)//2 for n in res]\n",
    "\n",
    "        return sum(ans)%M\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        sum=0\n",
    "        i=0\n",
    "        print(len(s))\n",
    "        while i<len(s) :\n",
    "            num=1\n",
    "            while i<len(s)-1 and s[i]==s[i+1]:\n",
    "                num=num+1\n",
    "                i=i+1\n",
    "            sum=sum + (num+1)*num//2\n",
    "            print(sum)\n",
    "            i=i+1\n",
    "        return sum % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        sum=0\n",
    "        i=0\n",
    "        print(len(s))\n",
    "        while i<len(s) :\n",
    "            num=1\n",
    "            while i<len(s)-1 and s[i]==s[i+1]:\n",
    "                num=num+1\n",
    "                i=i+1\n",
    "            sum=sum + (num+1)*num//2\n",
    "            print(sum)\n",
    "            i=i+1\n",
    "        return sum % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        # build a dictionary \n",
    "        k_dict = {}\n",
    "        def find_subsequent(index):\n",
    "            c = s[index]\n",
    "            j = index \n",
    "            for i in range(index+1, len(s)):\n",
    "                if s[i] == c:\n",
    "                    j = i \n",
    "                else:\n",
    "                    return s[index:j+1], j\n",
    "            return s[index:j+1], j\n",
    "\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "        # for i, c in enumerate(s):\n",
    "            c = s[i]\n",
    "            if c in k_dict:\n",
    "                seq, i = find_subsequent(i)\n",
    "                k_dict[c].append(seq)\n",
    "            else:\n",
    "                seq, i = find_subsequent(i)\n",
    "                k_dict[c] = [seq]\n",
    "            i += 1\n",
    "\n",
    "        \n",
    "        # for k,v in k_dict.items():\n",
    "        #     print(k, v)\n",
    "\n",
    "        # count\n",
    "        _sum = 0 \n",
    "        for k, v in k_dict.items():\n",
    "            # get max_\n",
    "            _max = 0\n",
    "            for item in v:\n",
    "                _max = max(_max, len(item))\n",
    "            # calculate \n",
    "            for i in range(1, _max+1):\n",
    "                for item in v:\n",
    "                    if i <= len(item):\n",
    "                        _sum += len(item) - i + 1 \n",
    "                        _sum %= 10**9 + 7\n",
    "        \n",
    "        return _sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        start, stop = 0, 1\n",
    "        l =[]\n",
    "        re = 0\n",
    "        while stop < n:\n",
    "            if s[start] != s[stop]:\n",
    "                l.append(s[start:stop])\n",
    "                start = stop \n",
    "            stop += 1\n",
    "        l.append(s[start:])\n",
    "        for e in l:\n",
    "            re += (1 + len(e)) * len(e) / 2\n",
    "        return int(re) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n >> 1\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        a = 0\n",
    "        i = 0\n",
    "        lis = []\n",
    "        while i < len(s):\n",
    "            cha = s[i]\n",
    "            # lis.append(cha)\n",
    "            for j in range(i+1,len(s)+1):\n",
    "                if j == len(s):\n",
    "                    lis.append(cha)\n",
    "                    break\n",
    "                if s[i]!=s[j]:\n",
    "                    lis.append(cha)\n",
    "                    break\n",
    "                else:\n",
    "                    cha+=s[j]\n",
    "            i = j\n",
    "        # lis = set(lis)\n",
    "        print(lis)\n",
    "        for i in lis:\n",
    "\n",
    "            a += (len(i)+1)*len(i)//2\n",
    "        return a%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        mod=10**9+7\n",
    "        arr=[(k,len(list(v))) for k,v in itertools.groupby(s)]\n",
    "        res=0\n",
    "        for k,v in arr:\n",
    "            res+=(v+1)*v//2\n",
    "        \n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        mod=10**9+7\n",
    "        arr=[(k,len(list(v))) for k,v in itertools.groupby(s)]\n",
    "        res=0\n",
    "        for k,v in arr:\n",
    "            res+=(v+1)*v//2\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "\n",
    "        sum=0\n",
    "        cur=''\n",
    "        li=[]\n",
    "        for i in range(len(s)):\n",
    "            if cur!=s[i]:\n",
    "                li.append(s[i])\n",
    "                cur=s[i]\n",
    "            else:\n",
    "                li[-1]+=cur\n",
    "        for i in li:\n",
    "            sum+=(1+len(i))*len(i)//2\n",
    "            \n",
    "        print(li)\n",
    "        return sum%(10**9 + 7)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        M = 10**9 + 7\n",
    "        i, j = 0, 0\n",
    "        res = []\n",
    "        while i < len(s) and j < len(s):\n",
    "            while j < len(s) and s[j] == s[i]:\n",
    "                j += 1\n",
    "            res.append(j-i)\n",
    "            i = j\n",
    "        ans = [n*(n+1)//2 for n in res]\n",
    "\n",
    "        return sum(ans)%M\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        ans = [(i, len(list(j))) for i, j in groupby(s)]\n",
    "        for i, j in ans:\n",
    "            res += j * (j + 1) // 2\n",
    "            res %= 10 ** 9 + 7\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        # groupby，把字符串分成由相同字符组成的字符串组\n",
    "        for _, g in groupby(s):\n",
    "            group = list(g)\n",
    "            print(group)\n",
    "            n = len(group)\n",
    "            ans += n * (n + 1) // 2\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res = res + (n*(n+1))//2\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        factor = pow(10, 9) + 7\n",
    "        i, n = 0, len(s)\n",
    "        ans = 0\n",
    "        s = list(s)\n",
    "        while i < n:\n",
    "            start = i\n",
    "            while i < n - 1 and s[i] == s[i + 1]:\n",
    "                i += 1          \n",
    "            i += 1\n",
    "            k = i - start\n",
    "            ans += (k * k - (k * (k - 1) >> 1)) % factor\n",
    "        \n",
    "        return ans % factor\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        # 统计连续字符即可\n",
    "        res = 0\n",
    "        for k, g in itertools.groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += n * (n + 1) // 2 % MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n + 1) * n // 2\n",
    "\n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        res = 0\n",
    "        \n",
    "        for k, v in groupby(s):\n",
    "            cnt = len(list(v))\n",
    "            res += cnt * (cnt + 1) // 2\n",
    "\n",
    "        return res % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k,g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += (n+1)*n//2\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for k, g in groupby(s):\n",
    "            n = len(list(g))\n",
    "            res += n * (n + 1) // 2\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        info = []\n",
    "        for ch in s:\n",
    "            if not info or info[-1][0] != ch:\n",
    "                info.append([ch, 1])\n",
    "            else:\n",
    "                info[-1][1] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for ch, cnt in info:\n",
    "            ans += ((cnt * (cnt + 1)) // 2) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countHomogenous(self, s: str) -> int:\n",
    "        factor = pow(10, 9) + 7\n",
    "        i, n = 0, len(s)\n",
    "        ans = 0\n",
    "        s = list(s)\n",
    "        while i < n:\n",
    "            start = i\n",
    "            while i < n - 1 and s[i] == s[i + 1]:\n",
    "                i += 1          \n",
    "            i += 1\n",
    "            k = i - start\n",
    "            ans += k * k - (k * (k - 1) >> 1)\n",
    "        \n",
    "        return ans % factor\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
